#include <iostream>
#include <string.h>
#include <time.h>
#include <stdio.h>
int fibo(int a[], int n);
int helper(int n);
//备忘录需要存储 f(1),f(2),...,f(n)
int helper(int n)
{
    int a[n+1];
    memset(a, 0, sizeof(a));
    a[1] = 1;
    if (n >= 2)
        a[2] = 1;
    return fibo(a, n);
}
int fibo(int a[], int n)
{
    if (n == 1 || n == 2) return 1;
    if (a[n] != 0) return a[n];
    else
    {
        a[n] = fibo(a, n-1) + fibo(a, n-2);
        return a[n];
    }
}
int main()
{
    using namespace std;

    int begin, end;
    begin = clock();
    cout << helper(45) << endl;
    end = clock();
    cout << "using " << end - begin << endl;
    return 0;
}
// 1 1 2 3 5 8 13 21 